package reviewAlgorithms.search;

import java.util.ArrayList;
import java.util.List;

public class PacificAtlantic {
    public static void main(String[] args) {
        int[][] matrix = {
                {1,2,2,3,5},
                {3,2,3,4,4},
                {2,4,5,3,1},
                {6,7,1,4,5},
                {5,1,1,2,4}
        };
        List<List<Integer>> res = pacificAtlantic(matrix);
        if (res.size() > 0){
            for (List<Integer> item: res ){
                System.out.println(item);
            }
        }

    }
    public static List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<>();
        if (matrix == null || matrix.length < 1){
            return res;
        }
        int rowNum = matrix.length;
        int columnNum = matrix[0].length;
        int maxNum = rowNum * columnNum;
        for (int i = 0; i < maxNum; i++) {
            int row = i / columnNum;
            int column = i % columnNum;
            List<Integer> oneRes;
            if (isPacificAtlantic(row,column,matrix)){
                oneRes = new ArrayList<>();
                oneRes.add(row);
                oneRes.add(column);
                res.add(oneRes);
            }
        }
        return res;
    }

    private static boolean isPacificAtlantic(int row, int column ,int[][] matrix) {
        int[][] state = new int[matrix.length][matrix[0].length];
        boolean[] booleans = new boolean[2];
        isArrive(row,column,state,matrix,booleans);
        return booleans[0] && booleans[1];
    }

    private static void isArrive(int row, int column, int[][] state, int[][] matrix, boolean[] booleans) {
        if (row >= matrix.length - 1 || column >= matrix[0].length - 1){
            booleans[1] = true;
        }
        if (row <= 0 || column <= 0){
            booleans[0] = true;
        }
        if (booleans[0] && booleans[1]){
            return;
        }
        if (state[row][column] == 0){
            state[row][column] = 1;
            if (row + 1 < matrix.length && matrix[row + 1][column] <= matrix[row][column]){
                isArrive(row + 1 ,column, state, matrix,booleans);
            }
            if (column + 1 < matrix[0].length && matrix[row][column + 1] <= matrix[row][column]){
                isArrive(row,column + 1, state, matrix,booleans);
            }
            if (row - 1 >= 0 && matrix[row - 1][column] <= matrix[row][column]){
                isArrive(row - 1 ,column, state, matrix,booleans);
            }
            if (column - 1 >= 0 && matrix[row][column - 1] <= matrix[row][column]){
                isArrive(row,column - 1, state, matrix,booleans);
            }
        }
    }
}
